package org.niu.array;

import java.util.*;

public class IPO {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int cur = w;
        PriorityQueue<AbstractMap.SimpleEntry<Integer,Integer>> q = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                if(o1!=o2) return o2.getValue()-o1.getValue();
                else return o1.getKey() - o2.getKey();
            }
        });
        for(int i = 0;i < profits.length;i++){
            q.add(new AbstractMap.SimpleEntry<>(capital[i],profits[i]));
        }
        List<AbstractMap.SimpleEntry<Integer,Integer>> list = new ArrayList<>();
        while(k > 0 && !q.isEmpty()){
            k--;
            while(!q.isEmpty() && cur < q.peek().getKey()){
                list.add(q.poll());
            }
            if(q.isEmpty()) break;
            AbstractMap.SimpleEntry<Integer, Integer> toDelete = q.poll();
            cur += toDelete.getValue();
            q.addAll(list);
            list.clear();
        }
        return cur;
    }
}
